package chapter04_RecursionAndDynamic.queen;

/**
 * 描述：八皇后问题
 *      在8*8的棋盘中摆放8个皇后，任意两个皇后不能处在同一行、同一列或同一斜线上
 *
 * @author hl
 * @date 2021/7/31 20:55
 */
public class EightQueen {
    public static void main(String[] args) {
        EightQueen main = new EightQueen();
        int num1 = main.num1(8);
        System.out.println(num1);
        int num2 = main.num2(8);
        System.out.println(num2);
    }

    /**
     * 回溯法
     * 16皇后：298365
     * @param n
     * @return
     */
    public int num1(int n){
        if (n < 1) {
            return 0;
        }
        int[] record = new int[n];
        return process1(record, 0, n);
    }

    private int process1(int[] record, int i, int n) {
        if (i == n) {
            return 1;
        }
        int res = 0;
        for (int j = 0; j < n; j++) {
            if (isValid(record, i, j)) {
                record[i] = j;
                res += process1(record, i + 1, n);
            }
        }
        return res;
    }

    private boolean isValid(int[] record, int i, int j) {
        for (int k = 0; k < i; k++) {
            if (record[k] == j || Math.abs(record[k] - j) == i - k) {
                return false;
            }
        }
        return true;
    }

    public int num2(int n){
        /**
         * 因为本方法中位运算的载体是int型变量，所有只能算1~32皇后问题，如果想计算更多皇后请使用包含更多位的变量
         */
        if (n < 1 || n > 32) {
            return 0;
        }
        int upperLim = n == 32 ? -1 : (1 << n) - 1;
        return process2(upperLim, 0, 0, 0);
    }

    /**
     *
     * @param upperLim  代表初始时哪些位置可以防止变量，可以防止的位置为1，不能放置的位置为0
     * @param colLim    表示当前的上一行放置的皇后，1表示已经放置，0表示未放置
     * @param leftDiaLim    表示当前行的位置是否在前面的皇后的左斜线位置上，如果在则为1，如果不在则为0
     * @param rightDiaLim   表示当前行的位置是否在前面的皇后的右斜线位置上，如果在则为1，如果不在则为0
     * @return
     */
    private int process2(int upperLim, int colLim, int leftDiaLim, int rightDiaLim) {
        if (colLim == upperLim) {
            return 1;
        }
        int res = 0;
        //表示当前行的可选择位置的最右一个位置
        int mostRightOne = 0;
        //当前行可选择的位置，1表示可以选择，0表示不能选择
        int pos = upperLim & (~ (colLim | leftDiaLim | rightDiaLim));
        //从右到左遍历当前行可选择的位置
        while(pos != 0){
            //找到pos当前最右边的1
            mostRightOne = pos & (~pos + 1);
            //移除pos最右边的1
            pos = pos - mostRightOne;
            res += process2(upperLim, colLim | mostRightOne, (leftDiaLim | mostRightOne) << 1, (rightDiaLim | mostRightOne) >>> 1);
        }
        return res;
    }
}
